package InsertSort;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 26
 *@time:      19:31
 *
 */

import java.lang.reflect.Array;
import java.util.Arrays;

//希尔排序--缩小增量排序
// 中心思想：先选定一个整数，把待排序文件中所有记录分成多个组，   --分组
// 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。    --组内排序（组内的每一次都是插入排序）
// 然后，取，重复上述分组和排序的工作。当到达=1时，           --重复
// 所有记录在统一组内排好序
public class ShellSort {

    //每一组进行直接插入排序
    private static void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if (arr[j] > tmp) {
                    arr[j+gap] = arr[j];
                }else {
                    //arr[j+gap] = tmp;
                    break;
                }
            }
            arr[j+gap] = tmp;

        }

    }

/*
* 时间复杂度：O(N^1.25 ~ N^1.5) -> N^1.3
* 空间复杂度：O(1)
* 稳定行：不稳定的排序
* */
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
       // shell(arr,1);
    }


    public static void main(String[] args) {
        int[] arr = {2,8,7,3,9,5,9,0,0,2};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }


}
